public class TopDownWithMemoization{

	public static void main(String [] args){
       int n=Integer.parseInt(args[0]);
	   int p[]={0,1,5,8,9,10,17,17,20,24,30};
	   memoizedCutRod(p,n);
	}

	public static int memoizedCutRod(int[] priceOfPerFoot,int numberOfFeet){
		int [] risk=new int[numberOfFeet+1];
		for(int i=0;i<=numberOfFeet;i++){
			risk[i]=-1;
		}
		return memoizedCutRodAux(priceOfPerFoot,numberOfFeet,risk);
	
	}
	public static int memoizedCutRodAux(int[] priceOfPerFoot,int numberOfFeet,int[] risk){
		System.out.println("==ss计算"+numberOfFeet+"应该怎么卖最合算");
		if(risk[numberOfFeet]>=0){
			return risk[numberOfFeet];
		}
		if (numberOfFeet==0){
		    System.out.println("呵呵！钢管长度为0？？你什么意思啊");
			return 0;
		}
		int q=-1;
		for(int i=1;i<=numberOfFeet;i++){
		    System.out.println("==mm比较"+numberOfFeet+"q开始："+q);
			q=Math.max(q,priceOfPerFoot[i]+memoizedCutRodAux(priceOfPerFoot,numberOfFeet-i,risk));
		    System.out.println("==mm比较"+numberOfFeet+"q结束："+q);
		}
		risk[numberOfFeet]=q;
		System.out.println("==ee计算"+numberOfFeet+"应该怎么卖最合算"+q);
		return q;
	}


}
